package codetop.microsoft.T32;

/**
 * @Author: 18362
 * @Create: 2022-08-14 9:14:25 星期日
 */
class Solution {
    public int longestValidParentheses(String s) {
        int[] dp = new int[s.length() + 1];
        for (int i=0; i<s.length(); ++i) {
            char c = s.charAt(i);
            if (c == '(')
                continue;
            int j = i - dp[i] - 1;
            if (i > 0 && j >= 0 && s.charAt(j) == '(')
                dp[i+1] = dp[i] + 2 + dp[i-dp[i]-1];
        }
        int res = 0;
        for (int i=1; i<dp.length; ++i)
            res = Math.max(res, dp[i]);
        return res;
    }
}